package LeetCode._02算法基础.day07广度深度优先搜索;

import LeetCode._01算法入门.day08广度深度优先搜索.Node;
import 题组.Solution;

import java.util.LinkedList;
import java.util.Queue;

/**
 * @author 挚爱之夕
 * @date 2022 - 03 - 17 - 12:12
 * @Description 填充它的每个 next 指针，让这个指针指向其下一个右侧节点。
 * 如果找不到下一个右侧节点，则将 next 指针设置为 NULL。
 * 初始状态下，所有next 指针都被设置为 NULL。
 * @Version 中等
 */
public class _117填充树同层next {

    /*by me 使用队列连接同层 太慢了*/
    public Node connect(Node root) {
        if(root == null)
            return null;
        Node leftMost = root;
        //记录同层
        Queue<Node> queue = new LinkedList<>();
        while(true){
            while(leftMost != null){
                //添加非空节点
                if(leftMost.left != null){
                    queue.add(leftMost.left);
                }
                if(leftMost.right != null){
                    queue.add(leftMost.right);
                }
                //右移
                leftMost = leftMost.next;
            }
            if(queue.isEmpty()){
                break;
            }
            leftMost = queue.peek();
            //队列里都是同层的
            while(!queue.isEmpty()){
                Node node = queue.remove();
                if(!queue.isEmpty()){
                    node.next = queue.peek();
                }
            }
        }

        return root;
    }

    /*官方思路 */

    //1.层次遍历
    public Node connect1(Node root) {
        if (root == null) {
            return null;
        }
        Queue<Node> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            int n = queue.size();
            //上一个节点
            Node last = null;
            for (int i = 1; i <= n; ++i) {

                Node f = queue.poll();
                if (f.left != null) {
                    queue.offer(f.left);
                }
                if (f.right != null) {
                    queue.offer(f.right);
                }
                if (i != 1) {
                    last.next = f;
                }
                last = f;
            }
        }
        return root;
    }
    //2.使用已经建立的next指针

    /*
    位于第 x 层时为第 x + 1 层建立 next 指针。
    每次只要知道下一层的最左边的节点，就可以从该节点开始，像遍历链表一样遍历该层的所有节点。
     */

    //上一个节点
    Node last = null;
    //同层最左端节点
    Node nextStart = null;
    public Node connect2(Node root) {
        if (root == null) {
            return null;
        }
        Node start = root;
        while (start != null) {
            last = null;
            nextStart = null;
            //该层通过next形成了一个链表，为其下一层创建next
            for (Node p = start; p != null; p = p.next) {
                //处理下一层
                if (p.left != null) {
                    handle(p.left);
                }
                if (p.right != null) {
                    handle(p.right);
                }
            }
            start = nextStart;
        }
        return root;
    }

    public void handle(Node p) {
        //填充next
        if (last != null) {
            last.next = p;
        }
        //记录下一层开始
        if (nextStart == null) {
            nextStart = p;
        }
        last = p;
    }
}
